package Lee_code;

import java.util.*;
public class Lee_17 {
    int target_len;
    char[] in;
    List<String> res = new LinkedList<String>();
    public List<String> letterCombinations(String digits) {
        in = digits.toCharArray();
        target_len = in.length;
        List<String> list = new LinkedList<>();
        Backtrace(list, 1);
        StringBuilder sb = new StringBuilder();

        return res;
    }

    private void Backtrace(List<String> strings, int start_index) {
        if (strings.size()==target_len)
        {
            List<String> temp = new LinkedList<>(strings);
            res.add(temp.toString());
        }
        else {
            if(in[start_index]=='2')
            {
                strings.add("a");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("b");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("c");
                Backtrace(strings, start_index+1);
            }
            if(in[start_index]=='3')
            {
                strings.add("d");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("e");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("f");
                Backtrace(strings, start_index+1);
            }
            if(in[start_index]=='4')
            {
                strings.add("g");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("h");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("i");
                Backtrace(strings, start_index+1);
            }
            if(in[start_index]=='5')
            {
                strings.add("j");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("k");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("l");
                Backtrace(strings, start_index+1);
            }
            if(in[start_index]=='6')
            {
                strings.add("m");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("n");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("o");
                Backtrace(strings, start_index+1);
            }
            if(in[start_index]=='7')
            {
                strings.add("p");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("q");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("r");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("s");
                Backtrace(strings, start_index+1);
            }
            if(in[start_index]=='8')
            {
                strings.add("t");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("u");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("v");
                Backtrace(strings, start_index+1);
            }
            if(in[start_index]=='9')
            {
                strings.add("w");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("x");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("y");
                Backtrace(strings, start_index+1);
                strings.remove(strings.size()-1);
                strings.add("z");
                Backtrace(strings, start_index+1);
            }
        }

    }


    public static void main(String[] args) {

    }
}
